
public class LRU {
	DoubleNode head = null;
	int count = 0;

	int size;

	public LRU(int size) {
		this.size = size;
	}

	public void setValue(int value) {
		if (head == null) {
			head = new DoubleNode(value);
			count++;
			return;
		}
		if (count < size) {
			DoubleNode tmp = head;
			while(tmp != null) {
				if(tmp.value == value) {
					break;
				}
				tmp = tmp.next;
			}
			//没找到-- 插入
			if(tmp == null) {
				DoubleNode node = new DoubleNode(value);
				node.next = head;
				head.pre = node;
				head = node;
				count++;
			}else {//找到了 --移动到头结点
				head = move(head, tmp);
			}
		}else {
			DoubleNode tmp = head;
			DoubleNode last = head;
			while(tmp != null) {
				last = tmp;
				if(tmp.value == value) {
					break;
				}
				tmp = tmp.next;
			}
			if(tmp == null) {//没找到-- 插入 并删除尾结点
				DoubleNode node = new DoubleNode(value);
				node.next = head;
				head.pre = node;
				head = node;
				DoubleNode pre = last.pre;
				pre.next = null;
				last = null;
			}else {//找到了 --移动到头结点
				head = move(head, tmp);
			}
		}

	}

	public int getValue(int value) {
		if(head != null) {
			DoubleNode tmp = head;
			while(tmp != null) {
				if(tmp.value == value) {
					break;
				}
				tmp = tmp.next;
			}
			if(tmp != null) {
				head = move(head, tmp);
				return tmp.value;
			}
			
		}
		return -1;
	}

	private static DoubleNode move(DoubleNode head, DoubleNode node) {
		if (head == node) {
			return head;
		}
		DoubleNode pre = node.pre;
		DoubleNode next = node.next;
		pre.next = next;
		if (next != null) {
			next.pre = pre;
		}
		node.next = head;
		node.pre = null;
		head.pre = node;
		return node;
	}
}
